0001 // 0002 // BigUInt Subtraction.swift 0003 // BigInt 0004 // 0005 // Created by Károly Lőrentey on 2016-01-03. 0006 // Copyright © 2016 Károly Lőrentey. All rights reserved. 0007 // 0008 0009 import Foundation 0010 0011 extension BigUInt { 0012 //MARK: Subtraction 0013 0014 /// Subtract a digit `d` from this integer in place, returning a flag that is true if the operation 0015 /// caused an arithmetic overflow. `d` is shifted `shift` digits to the left before being subtracted. 0016 /// 0017 /// - Note: If the result is true, then `self` becomes the two's complement of the absolute difference. 0018 /// - Complexity: O(count) 0019 @warn_unused_result 0020 public mutating func subtractDigitInPlaceWithOverflow(d: Digit, shift: Int = 0) -> Bool { 0021 precondition(shift >= 0) 0022 lift() 0023 var carry: Digit = d 0024 var i = shift 0025 while carry > 0 && i < count { 0026 let (d, c) = Digit.subtractWithOverflow(self[i], carry) 0027 self[i] = d 0028 carry = (c ? 1 : 0) 0029 i += 1 0030 } 0031 return carry > 0 0032 } 0033 0034 /// Subtract a digit `d` from this integer, returning the difference and a flag that is true if the operation 0035 /// caused an arithmetic overflow. `d` is shifted `shift` digits to the left before being subtracted. 0036 /// 0037 /// - Note: If `overflow` is true, then the returned value is the two's complement of the absolute difference. 0038 /// - Complexity: O(count) 0039 @warn_unused_result 0040 public func subtractDigitWithOverflow(d: Digit, shift: Int = 0) -> (BigUInt, overflow: Bool) { 0041 var result = self 0042 let overflow = result.subtractDigitInPlaceWithOverflow(d, shift: shift) 0043 return (result, overflow) 0044 } 0045 0046 /// Subtract a digit `d` from this integer in place. 0047 /// `d` is shifted `shift` digits to the left before being subtracted. 0048 /// 0049 /// - Requires: self >= d * 2^shift 0050 /// - Complexity: O(count) 0051 public mutating func subtractDigitInPlace
BigUInt Subtraction.swift:42 BigUInt Subtraction.swift:52 (d: Digit, shift: Int = 0) { 0052 let overflow = subtractDigitInPlaceWithOverflow(d, shift: shift) 0053 precondition(!overflow) 0054 } 0055 0056 /// Subtract a digit `d` from this integer and return the result. 0057 /// `d` is shifted `shift` digits to the left before being subtracted. 0058 /// 0059 /// - Requires: self >= d * 2^shift 0060 /// - Complexity: O(count) 0061 @warn_unused_result 0062 public func subtractDigit(d: Digit, shift: Int = 0) -> BigUInt { 0063 var result = self 0064 result.subtractDigitInPlace(d, shift: shift) 0065 return result 0066 } 0067 0068 /// Subtract `b` from this integer in place, and return true iff the operation caused an 0069 /// arithmetic overflow. `b` is shifted `shift` digits to the left before being subtracted. 0070 /// 0071 /// - Note: If the result is true, then `self` becomes the twos' complement of the absolute difference. 0072 /// - Complexity: O(count) 0073 @warn_unused_result 0074 public mutating func subtractInPlaceWithOverflow
BigUInt Subtraction.swift:64 BigUInt Subtraction.swift:135 (b: BigUInt, shift: Int = 0) -> Bool { 0075 precondition(shift >= 0) 0076 lift() 0077 var carry = false 0078 var bi = 0 0079 while bi < b.count || (shift + bi < count && carry) { 0080 let ai = shift + bi 0081 let (d, c) = Digit.subtractWithOverflow(self[ai], b[bi]) 0082 if carry { 0083 let (d2, c2) = Digit.subtractWithOverflow(d, 1) 0084 self[ai] = d2 0085 carry = c || c2 0086 } 0087 else { 0088 self[ai] = d 0089 carry = c 0090 } 0091 bi += 1 0092 } 0093 return carry 0094 } 0095 0096 /// Subtract `b` from this integer, returning the difference and a flag that is true if the operation caused an 0097 /// arithmetic overflow. `b` is shifted `shift` digits to the left before being subtracted. 0098 /// 0099 /// - Note: If `overflow` is true, then the result value is the twos' complement of the absolute value of the difference. 0100 /// - Complexity: O(count) 0101 @warn_unused_result 0102 public func subtractWithOverflow(b: BigUInt, shift: Int = 0) -> (BigUInt, overflow: Bool) { 0103 var result = self 0104 let overflow = result.subtractInPlaceWithOverflow(b, shift: shift) 0105 return (result, overflow) 0106 } 0107 0108 /// Subtract `b` from this integer in place. 0109 /// `b` is shifted `shift` digits to the left before being subtracted. 0110 /// 0111 /// - Requires: self >= b * 2^shift 0112 /// - Complexity: O(count) 0113 public mutating func subtractInPlace
BigUInt Subtraction.swift:104 BigUInt Subtraction.swift:114 (b: BigUInt, shift: Int = 0) { 0114 let overflow = subtractInPlaceWithOverflow(b, shift: shift) 0115 precondition(!overflow) 0116 } 0117 0118 /// Subtract `b` from this integer, and return the difference. 0119 /// `b` is shifted `shift` digits to the left before being subtracted. 0120 /// 0121 /// - Requires: self >= b * 2^shift 0122 /// - Complexity: O(count) 0123 @warn_unused_result 0124 public func subtract
BigUInt Division.swift:151 BigUInt Division.swift:156 BigUInt Multiplication.swift:153 BigUInt Subtraction.swift:126 BigUInt Subtraction.swift:155 (b: BigUInt, shift: Int = 0) -> BigUInt { 0125 var result = self 0126 result.subtractInPlace(b, shift: shift) 0127 return result 0128 } 0129 0130 /// Decrement this integer by one. 0131 /// 0132 /// - Requires: !isZero 0133 /// - Complexity: O(count) 0134 public mutating func decrement(shift shift: Int = 0) { 0135 self.subtractDigitInPlace(1, shift: shift) 0136 } 0137 } 0138 0139 //MARK: Subtraction 0140 0141 /// Subtract `b` from `a` and return the result. 0142 /// 0143 /// - Requires: a >= b 0144 /// - Complexity: O(a.count) 0145 @warn_unused_result 0146 public func -(a: BigUInt, b: BigUInt) -> BigUInt { 0147 return a.subtract(b) 0148 } 0149 0150 /// Subtract `b` from `a` and store the result in `a`. 0151 /// 0152 /// - Requires: a >= b 0153 /// - Complexity: O(a.count) 0154 public func -=(inout a: BigUInt, b: BigUInt) { 0155 a.subtractInPlace(b, shift: 0) 0156 } 0157
BigUInt Subtraction.swift:147